﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.SortCode
{
    class BubbleSort
    {
        //=====================================冒泡排序
        //思路：冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒
        //它重复地走访要排序的数列，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
        //对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
        //针对所有的元素重复以上的步骤，除了最后一个。
        //持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
        //平均时间复杂度：O(N^2)
        //最佳时间复杂度：O(N) 当输入的数据已经是正序时
        //最差时间复杂度：O(N^2) 当输入的数据是反序时
        //空间复杂度：O(1)


        public void Sort(int[] arr)
        {
            for(int i = 0;i<arr.Length-1;i++)//比较n-1轮
            {
                for(int j = 0;j<arr.Length-1-i;j++)//每轮比较n-1-i次,
                {
                    if(arr[j] > arr[j+1])// 相邻元素两两对比
                    {
                        int temp = arr[j + 1]; // 元素交换
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    }
}
